function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val)
    this.next = (next===undefined ? null : next)
}
/**
 * 1.两数相加
 * 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
 * 请你将两个数相加，并以相同形式返回一个表示和的链表。
 * 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
 * 输入 l1=[7,0,3] l2=[5,6,4]
 * 输出 [7,0,8]
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    let tmp = l1.val + l2.val;
    let rtn = pointer = new ListNode(tmp % 10);
    let t1 = l1,
        t2 = l2;
    while(t1.next || t2.next) {
        if (t1.next && t2.next) {
            t1 = t1.next;
            t2 = t2.next;
            tmp = Math.floor(tmp / 10) + t1.val + t2.val;
            pointer = pointer.next = new ListNode(tmp % 10);
        } else if (t1.next) {
            do {
                t1 = t1.next;
                tmp = Math.floor(tmp / 10) + t1.val;
                pointer = pointer.next = new ListNode(tmp % 10);
            } while (t1.next);
        } else {
            do {
                t2 = t2.next;
                tmp = Math.floor(tmp / 10) + t2.val;
                pointer = pointer.next = new ListNode(tmp % 10);
            } while (t2.next);
        }
    }
    if (tmp > 9) {
        pointer.next = new ListNode(1);
    }
    return rtn;
};
/**
 * 2.奇偶链表
 * 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
 * 请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
 * @param {ListNode} head
 * @return {ListNode}
 */
var oddEvenList = function(head) {
    if (head === null) {
        return null;
    }
    let evenHead = head.next;
    let odd = head, even = evenHead;
    while (even !== null && even.next !== null) {
        odd.next = even.next;
        odd = odd.next;
        even.next = odd.next;
        even = even.next;
    }
    odd.next = evenHead;
    // let index = 1;
    // let even = tmp = null;
    // let node = head;
    // while (node && node.next) {
    //     if (index % 2 === 1) {
    //         if (tmp) {
    //             tmp = tmp.next = node.next;
    //         } else {
    //             even = tmp = node.next;
    //         }
    //         node.next = node.next.next;
    //         tmp.next = null;
    //         ++index;
    //     } 
    //     node = node.next;
    //     ++index;
    // }
    // tmp = head;
    // while (tmp.next) {
    //     tmp = tmp.next;
    // }
    // tmp.next = even;
    return head;
};
/**
 * 3.相交链表
 * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
 * 题目数据 保证 整个链式结构中不存在环。
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    if (!headA || !headB) {
        return null;
    }
    // 双指针
    let a = headA,
        b = headB;
    while (a !== b) {
        a = a ? a.next : headA;
        b = b ? b.next : headB;
    }
    return a;
    // let lenA = lenB = 1,
    //     a = headA,
    //     b = headB;
    // while (a.next) {
    //     a = a.next;
    //     ++lenA;
    // }
    // while (b.next) {
    //     b = b.next;
    //     ++lenB;
    // }
    // a = headA;
    // b = headB;
    // if (lenA > lenB) {
    //     let d = lenA - lenB;
    //     while (d > 0) {
    //         a = a.next;
    //         --d;
    //     }
    // } else if (lenA < lenB) {
    //     let d = lenB - lenA;
    //     while (d > 0) {
    //         b = b.next;
    //         --d;
    //     }
    // }
    // while (a !== b) {
    //     a = a.next;
    //     b = b.next;
    // }
    // return a;
};